
<!DOCTYPE html>
<html lang="zh-CN" class="loading">
<head>
    <meta charset="UTF-8" />
    <meta http-equiv="X-UA-Compatible" content="IE=edge,chrome=1" />
    <meta name="viewport" content="width=device-width, minimum-scale=1.0, maximum-scale=1.0, user-scalable=no">
    <title>leetcode863. 二叉树中所有距离为 K 的结点 - peony&#39;s blogs</title>
    <meta name="apple-mobile-web-app-capable" content="yes" />
    <meta name="apple-mobile-web-app-status-bar-style" content="black-translucent">
    <meta name="google" content="notranslate" />
    <meta name="keywords" content="peony,"> 
    <meta name="description" content="leetcode863. 二叉树中所有距离为 K 的结点

给定一个二叉树（具有根结点 root）， 一个目标结点 target ，和一个整数值 K 。


返回到目标结点 target 距离为 K,"> 
    <meta name="author" content="peony"> 
    <link rel="alternative" href="atom.xml" title="peony&#39;s blogs" type="application/atom+xml"> 
    <link rel="icon" href="/img/favicon63.png"> 
    
<link rel="stylesheet" href="//cdn.jsdelivr.net/npm/gitalk@1/dist/gitalk.css">

    
<link rel="stylesheet" href="/css/diaspora.css">

    <script async src="//pagead2.googlesyndication.com/pagead/js/adsbygoogle.js"></script>
    <script>
         (adsbygoogle = window.adsbygoogle || []).push({
              google_ad_client: "ca-pub-8691406134231910",
              enable_page_level_ads: true
         });
    </script>
    <script async custom-element="amp-auto-ads"
        src="https://cdn.ampproject.org/v0/amp-auto-ads-0.1.js">
    </script>
<meta name="generator" content="Hexo 4.2.0"></head>

<body class="loading">
    <span id="config-title" style="display:none">peony&#39;s blogs</span>
    <div id="loader"></div>
    <div id="single">
    <div id="top" style="display: block;">
    <div class="bar" style="width: 0;"></div>
    <a class="icon-home image-icon" href="javascript:;" data-url="http://yoursite.com"></a>
    <div title="播放/暂停" class="icon-play"></div>
    <h3 class="subtitle">leetcode863. 二叉树中所有距离为 K 的结点</h3>
    <div class="social">
        <!--<div class="like-icon">-->
            <!--<a href="javascript:;" class="likeThis active"><span class="icon-like"></span><span class="count">76</span></a>-->
        <!--</div>-->
        <div>
            <div class="share">
                <!--<a title="获取二维码" class="icon-scan" href="javascript:;" ></a>-->
            </div>
            <div id="qr"></div>
        </div>
    </div>
    <div class="scrollbar"></div>
</div>

    <div class="section">
        <div class="article">
    <div class='main'>
        <h1 class="title">leetcode863. 二叉树中所有距离为 K 的结点</h1>
        <div class="stuff">
            <span>三月 22, 2020</span>
            

        </div>
        <div class="content markdown">
            <h1 id="leetcode863-二叉树中所有距离为-K-的结点"><a href="#leetcode863-二叉树中所有距离为-K-的结点" class="headerlink" title="leetcode863. 二叉树中所有距离为 K 的结点"></a>leetcode863. 二叉树中所有距离为 K 的结点</h1><hr>
<blockquote>
<p>给定一个二叉树（具有根结点 root）， 一个目标结点 target ，和一个整数值 K 。</p>
</blockquote>
<blockquote>
<p>返回到目标结点 target 距离为 K 的所有结点的值的列表。 答案可以以任何顺序返回。</p>
</blockquote>
<blockquote>
<p>示例 1：</p>
</blockquote>
<blockquote>
<p>输入：root = [3,5,1,6,2,0,8,null,null,7,4], target = 5, K = 2</p>
</blockquote>
<blockquote>
<p>输出：[7,4,1]</p>
</blockquote>
<blockquote>
<p>解释：<br>所求结点为与目标结点（值为 5）距离为 2 的结点，<br>值分别为 7，4，以及 1<br><img src="https://imgconvert.csdnimg.cn/aHR0cHM6Ly9zMy1sYy11cGxvYWQuczMuYW1hem9uYXdzLmNvbS91cGxvYWRzLzIwMTgvMDYvMjgvc2tldGNoMC5wbmc?x-oss-process=image/format,png" alt="在这里插入图片描述"><br>提示：</p>
<ul>
<li>给定的树是非空的，且最多有 K 个结点。</li>
<li>树上的每个结点都具有唯一的值 0 &lt;= node.val &lt;= 500 。</li>
<li>目标结点 target 是树上的结点。</li>
<li>0 &lt;= K &lt;= 1000.</li>
</ul>
</blockquote>
<h3 id="思路一-转化成图-再变成bfs"><a href="#思路一-转化成图-再变成bfs" class="headerlink" title="思路一:转化成图,再变成bfs"></a>思路一:转化成图,再变成bfs</h3><p>遍历一次树,主要是为了把当前节点的父节点记录下来,这样bfs时候可以访问到父节点了.</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Solution</span> </span>&#123;</span><br><span class="line">    HashMap&lt;TreeNode,TreeNode&gt;map=<span class="keyword">new</span> HashMap&lt;&gt;();</span><br><span class="line">    ArrayList&lt;Integer&gt;list=<span class="keyword">new</span> ArrayList&lt;&gt;();</span><br><span class="line">    <span class="function"><span class="keyword">public</span> List&lt;Integer&gt; <span class="title">distanceK</span><span class="params">(TreeNode root, TreeNode target, <span class="keyword">int</span> K)</span> </span>&#123;</span><br><span class="line">        init(root,<span class="keyword">null</span>);</span><br><span class="line">        Queue&lt;TreeNode&gt;queue=<span class="keyword">new</span> LinkedList&lt;&gt;();</span><br><span class="line">        queue.offer(target);</span><br><span class="line">        Set&lt;TreeNode&gt;set=<span class="keyword">new</span> HashSet&lt;&gt;();</span><br><span class="line">        set.add(target);<span class="comment">//set防止重复访问某个节点</span></span><br><span class="line">        </span><br><span class="line">        <span class="keyword">while</span>(!queue.isEmpty())&#123;</span><br><span class="line">            <span class="keyword">int</span> size=queue.size();</span><br><span class="line">            <span class="keyword">if</span>(K==<span class="number">0</span>)&#123;</span><br><span class="line">                <span class="keyword">for</span>(TreeNode node:queue)&#123;</span><br><span class="line">                    list.add(node.val);</span><br><span class="line">                &#125;</span><br><span class="line">            &#125;</span><br><span class="line">            <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;size;i++)&#123;</span><br><span class="line">                TreeNode node=queue.poll();</span><br><span class="line">                <span class="keyword">if</span>(node.left!=<span class="keyword">null</span>&amp;&amp;!set.contains(node.left))&#123;</span><br><span class="line">                    queue.offer(node.left);</span><br><span class="line">                    set.add(node.left);</span><br><span class="line">                &#125;</span><br><span class="line">                <span class="keyword">if</span>(node.right!=<span class="keyword">null</span>&amp;&amp;!set.contains(node.right))&#123;</span><br><span class="line">                    queue.offer(node.right);</span><br><span class="line">                    set.add(node.right);</span><br><span class="line">                &#125;</span><br><span class="line">                <span class="keyword">if</span>(map.get(node)!=<span class="keyword">null</span>&amp;&amp;!set.contains(map.get(node)))&#123;</span><br><span class="line">                    queue.offer(map.get(node));</span><br><span class="line">                    set.add(map.get(node));</span><br><span class="line">                &#125;</span><br><span class="line">            &#125;</span><br><span class="line">            K--;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> list;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">init</span><span class="params">(TreeNode curNode,TreeNode parent)</span></span>&#123;</span><br><span class="line">        <span class="keyword">if</span>(curNode==<span class="keyword">null</span>)<span class="keyword">return</span>;</span><br><span class="line">        map.put(curNode,parent);</span><br><span class="line">        init(curNode.left,curNode);</span><br><span class="line">        init(curNode.right,curNode);</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h3 id="思路二-霍夫曼树"><a href="#思路二-霍夫曼树" class="headerlink" title="思路二:霍夫曼树"></a>思路二:霍夫曼树</h3><p>看到评论区有提示说霍夫曼树,我试着写了一下,左子树代表 <strong>1</strong>,右子树代表 <strong>3</strong> .用字符串表示每个节点的编号,任意两个节点之间的距离需要用前缀计算.<br>比如 <strong>113</strong>,和 <strong>131</strong>.前缀是1,所以是13(两位)+31(两位)=4(位).我是一条边一个编号,根节点编号为””.也就是空字符串.</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Solution</span> </span>&#123;</span><br><span class="line">    HashMap&lt;TreeNode,String&gt;map=<span class="keyword">new</span> HashMap&lt;&gt;();</span><br><span class="line">    <span class="keyword">public</span> TreeNode targetNode=<span class="keyword">null</span>;</span><br><span class="line">    <span class="function"><span class="keyword">public</span> List&lt;Integer&gt; <span class="title">distanceK</span><span class="params">(TreeNode root, TreeNode target, <span class="keyword">int</span> K)</span> </span>&#123;</span><br><span class="line">        map.put(root,<span class="string">""</span>);</span><br><span class="line">        init(root,<span class="string">""</span>);</span><br><span class="line">        <span class="keyword">return</span> traverse(target,map.get(target),K);</span><br><span class="line"></span><br><span class="line">    &#125;</span><br><span class="line">    <span class="function"><span class="keyword">public</span> List&lt;Integer&gt; <span class="title">traverse</span><span class="params">(TreeNode target,String targetString,<span class="keyword">int</span> k)</span></span>&#123;</span><br><span class="line">        ArrayList&lt;Integer&gt;list=<span class="keyword">new</span> ArrayList&lt;&gt;();</span><br><span class="line">        <span class="keyword">for</span>(TreeNode key:map.keySet())&#123;</span><br><span class="line">            <span class="keyword">int</span> diff=diff(map.get(key),targetString);<span class="comment">//计算路径</span></span><br><span class="line">            <span class="keyword">if</span>(diff==k)list.add(key.val);</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> list;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">diff</span><span class="params">(String s1,String s2)</span></span>&#123;</span><br><span class="line">        <span class="keyword">int</span> length=Math.min(s1.length(),s2.length());</span><br><span class="line">        <span class="keyword">int</span> i=<span class="number">0</span>;</span><br><span class="line">        <span class="keyword">for</span>(i=<span class="number">0</span>;i&lt;length;i++)&#123;</span><br><span class="line">            <span class="keyword">if</span>(s1.charAt(i)!=s2.charAt(i))<span class="keyword">break</span>;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> s1.length()-i+s2.length()-i;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">init</span><span class="params">(TreeNode node,String s)</span></span>&#123;<span class="comment">//对每个节点编号</span></span><br><span class="line">        <span class="keyword">if</span>(node==<span class="keyword">null</span>)<span class="keyword">return</span>;</span><br><span class="line">        <span class="keyword">if</span>(node.left!=<span class="keyword">null</span>)&#123;</span><br><span class="line">            StringBuffer sbf=<span class="keyword">new</span> StringBuffer(s);</span><br><span class="line">            sbf.append(<span class="string">"1"</span>);</span><br><span class="line">            map.put(node.left,<span class="keyword">new</span> String(sbf));</span><br><span class="line">            init(node.left,<span class="keyword">new</span> String(sbf));</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">if</span>(node.right!=<span class="keyword">null</span>)&#123;</span><br><span class="line">            StringBuffer sbf=<span class="keyword">new</span> StringBuffer(s);</span><br><span class="line">            sbf.append(<span class="string">"3"</span>);</span><br><span class="line">            map.put(node.right,<span class="keyword">new</span> String(sbf));</span><br><span class="line">            init(node.right,<span class="keyword">new</span> String(sbf));</span><br><span class="line">        &#125;</span><br><span class="line">        </span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h4 id="霍夫曼树2"><a href="#霍夫曼树2" class="headerlink" title="霍夫曼树2"></a>霍夫曼树2</h4><p>题解用long整数编码,而不是字符串,减少了一次for循环,并且根节点编号为1.</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br></pre></td><td class="code"><pre><span class="line">   <span class="class"><span class="keyword">class</span> <span class="title">Solution</span> </span>&#123;</span><br><span class="line">	Map&lt;Integer,Long&gt; map = <span class="keyword">new</span> HashMap&lt;&gt;();</span><br><span class="line">	<span class="function"><span class="keyword">public</span> List&lt;Integer&gt; <span class="title">distanceK</span><span class="params">(TreeNode root, TreeNode target, <span class="keyword">int</span> K)</span> </span>&#123;</span><br><span class="line">		List&lt;Integer&gt; list = <span class="keyword">new</span> ArrayList&lt;&gt;();</span><br><span class="line">		codeTree(root,<span class="number">1</span>);</span><br><span class="line">		<span class="keyword">long</span> targetCode = <span class="number">0</span>;</span><br><span class="line">    </span><br><span class="line">		<span class="keyword">for</span>(Integer key:map.keySet()) &#123;</span><br><span class="line">			<span class="keyword">if</span>(key==target.val) &#123;</span><br><span class="line">				targetCode = map.get(key);</span><br><span class="line">   				<span class="keyword">break</span>;</span><br><span class="line">			&#125;</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="keyword">for</span>(Integer key:map.keySet()) &#123;</span><br><span class="line">			<span class="keyword">if</span>(distanceCode(map.get(key),targetCode)==K) &#123;</span><br><span class="line">				list.add(key);</span><br><span class="line">			&#125;</span><br><span class="line">		&#125;</span><br><span class="line">	<span class="keyword">return</span> list;</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">codeTree</span><span class="params">(TreeNode root, <span class="keyword">long</span> value)</span></span>&#123;</span><br><span class="line">	<span class="keyword">if</span>(root==<span class="keyword">null</span>) <span class="keyword">return</span>;</span><br><span class="line">	map.put(root.val, value);</span><br><span class="line">	codeTree(root.right, value*<span class="number">10</span>+<span class="number">1</span>);</span><br><span class="line">	codeTree(root.left, value*<span class="number">10</span>+<span class="number">3</span>);</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">distanceCode</span> <span class="params">(<span class="keyword">long</span> val, <span class="keyword">long</span> target)</span> </span>&#123;</span><br><span class="line">	<span class="keyword">long</span> sameL = <span class="number">0</span>;</span><br><span class="line">	<span class="keyword">long</span> more = Math.max(val, target);</span><br><span class="line">	<span class="keyword">long</span> less = Math.min(val, target);</span><br><span class="line"></span><br><span class="line">	<span class="keyword">long</span> L1 =(<span class="keyword">long</span>)Math.log10(more)+<span class="number">1</span>;</span><br><span class="line">	<span class="keyword">long</span> L2 =(<span class="keyword">long</span>)Math.log10(less)+<span class="number">1</span>;</span><br><span class="line">    </span><br><span class="line">	<span class="keyword">double</span> temp = Math.abs(less*(Math.pow(<span class="number">10</span>, L1 - L2)) - more);</span><br><span class="line">	</span><br><span class="line">	sameL = (temp==<span class="number">0</span>)?L1:L1 - (<span class="keyword">long</span>)(Math.log10(temp+<span class="number">1</span>)) - <span class="number">1</span>;</span><br><span class="line">    </span><br><span class="line">	<span class="keyword">return</span> (<span class="keyword">int</span>)(L1 + L2 - <span class="number">2</span>*sameL);</span><br><span class="line">&#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p><strong>leetcode 58/100</strong></p>

            <!--[if lt IE 9]><script>document.createElement('audio');</script><![endif]-->
            <audio id="audio" loop="1" preload="auto" controls="controls" data-autoplay="false">
                <source type="audio/mpeg" src="">
            </audio>
            
                <ul id="audio-list" style="display:none">
                    
                        
                            <li title='0' data-url='http://link.hhtjim.com/163/5146554.mp3'></li>
                        
                    
                        
                            <li title='1' data-url='http://link.hhtjim.com/qq/001faIUs4M2zna.mp3'></li>
                        
                    
                </ul>
            
        </div>
        
    <div id='gitalk-container' class="comment link"
        data-ae='false'
        data-ci='c82ee42088349c609c4d'
        data-cs='541eefaa06715f3b1bcd6bf41cb69a4053d18348'
        data-r='PPeony.github.io'
        data-o='PPeony'
        data-a='PPeony'
        data-d='false'
    >查看评论</div>


    </div>
    
</div>


    </div>
</div>
</body>

<script src="//cdn.jsdelivr.net/npm/gitalk@1/dist/gitalk.min.js"></script>


<script src="//lib.baomitu.com/jquery/1.8.3/jquery.min.js"></script>
<script src="/js/plugin.js"></script>
<script src="/js/diaspora.js"></script>


<link rel="stylesheet" href="/photoswipe/photoswipe.css">
<link rel="stylesheet" href="/photoswipe/default-skin/default-skin.css">


<script src="/photoswipe/photoswipe.min.js"></script>
<script src="/photoswipe/photoswipe-ui-default.min.js"></script>


<!-- Root element of PhotoSwipe. Must have class pswp. -->
<div class="pswp" tabindex="-1" role="dialog" aria-hidden="true">
    <!-- Background of PhotoSwipe. 
         It's a separate element as animating opacity is faster than rgba(). -->
    <div class="pswp__bg"></div>
    <!-- Slides wrapper with overflow:hidden. -->
    <div class="pswp__scroll-wrap">
        <!-- Container that holds slides. 
            PhotoSwipe keeps only 3 of them in the DOM to save memory.
            Don't modify these 3 pswp__item elements, data is added later on. -->
        <div class="pswp__container">
            <div class="pswp__item"></div>
            <div class="pswp__item"></div>
            <div class="pswp__item"></div>
        </div>
        <!-- Default (PhotoSwipeUI_Default) interface on top of sliding area. Can be changed. -->
        <div class="pswp__ui pswp__ui--hidden">
            <div class="pswp__top-bar">
                <!--  Controls are self-explanatory. Order can be changed. -->
                <div class="pswp__counter"></div>
                <button class="pswp__button pswp__button--close" title="Close (Esc)"></button>
                <button class="pswp__button pswp__button--share" title="Share"></button>
                <button class="pswp__button pswp__button--fs" title="Toggle fullscreen"></button>
                <button class="pswp__button pswp__button--zoom" title="Zoom in/out"></button>
                <!-- Preloader demo http://codepen.io/dimsemenov/pen/yyBWoR -->
                <!-- element will get class pswp__preloader--active when preloader is running -->
                <div class="pswp__preloader">
                    <div class="pswp__preloader__icn">
                      <div class="pswp__preloader__cut">
                        <div class="pswp__preloader__donut"></div>
                      </div>
                    </div>
                </div>
            </div>
            <div class="pswp__share-modal pswp__share-modal--hidden pswp__single-tap">
                <div class="pswp__share-tooltip"></div> 
            </div>
            <button class="pswp__button pswp__button--arrow--left" title="Previous (arrow left)">
            </button>
            <button class="pswp__button pswp__button--arrow--right" title="Next (arrow right)">
            </button>
            <div class="pswp__caption">
                <div class="pswp__caption__center"></div>
            </div>
        </div>
    </div>
</div>




</html>
